package leetcode_day._2021._202106._0110;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/3 21:43
 * 连续数组
 * 算法：前缀和  哈希表
 * 做法和前一天的 523 差不多
 * 把 0 看成 -1，这样如果前缀和中出现 0，那么 0 和 1 的个数是一样的
 */
public class _03_525 {

    public int findMaxLength(int[] nums) {
        int m = nums.length;
        int[] pre = new int[m + 1];
        for (int i = 1; i <= m; i++) {
            int tmp = nums[i - 1] == 0 ? -1 : 1;
            pre[i] = pre[i - 1] + tmp;
        }
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 1; i <= m; i++) {
            if (pre[i] == 0) res = Math.max(res, i);
            else {
                if (map.containsKey(pre[i])) res = Math.max(res, i - map.get(pre[i]));
                else map.put(pre[i], i);
            }
        }
        return res;
    }

}
